/**
 * @file     longestCommonPrefix.js
 * @brief    [14. 最长公共前缀](https://leetcode.cn/problems/longest-common-prefix/description/)
 * @author   Zhu
 * @date     2023-06-07 00:59
 */

/**
 * 纵向对比
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function (strs) {
    let i = 0;
    let res = '';

    while (strs.length > 0) {
        let char = null;
        for (const str of strs) {
            if (!str[i]) {
                return res;
            }
            if (char == null) {
                char = str[i];
            } else {
                if (char !== str[i]) return res;
            }
        }
        i++;
        res += char;
    }

    return '';
};

/**
 * 迭代
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function (strs) {
    /* 求两个元素的lcp */
    function lcp(i, j) {
        let res = '';
        if (i.length > j.length) {
            [i, j] = [j, i];
        }
        for (let k = 0; k < i.length; k++) {
            if (i[k] === j[k]) res += i[k];
            else return res;
        }
        return res;
    }

    if (strs.length === 0) return '';
    if (strs.length === 1) return strs[0];
    return strs.reduce((a, c) => (a = lcp(a, c)));

    // let curIndex = strs.length - 1;
    // let curPrefix = strs[curIndex];
    // while (curIndex && curPrefix.length) {
    //     curPrefix = lcp(strs[--curIndex], curPrefix);
    // }
    // return curPrefix;
};

/**
 * 二分查找LCP的长度(LCP一定是前n个，其中n <= minLength)
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function (strs) {
    if (strs.length === 0) return '';

    const minLength = strs.reduce((a, c) => {
        a = Math.min(a, c.length);
        return a;
    }, strs[0].length);

    function isCommonPrefix(startIndex, endIndex) {
        for (; startIndex < endIndex; startIndex++) {
            for (let i = 1; i < strs.length; i++) {
                if (strs[0][startIndex] !== strs[i][startIndex]) return false;
            }
        }
        return true;
    }

    let i = 0,
        j = minLength;
    while (i < j) {
        let mid = i + Math.cel(j - i); // mid向上取, 因为要保证结束循环时，i的值就是要找的值
        if (isCommonPrefix(i, mid)) {
            i = mid;
        } else {
            j = mid - 1;
        }
    }

    return strs[0].slice(0, i);
};
